#coding=utf-8
# 插入排序
def ins_sort_rec(numlist:list, n:int)->None:
    '''
    :param numlist: 排序的数组
    :param n: 数组最后一个元素的序号
    复杂度为O(n2)
    :return:
    '''
    if n == 0:
        return
    ins_sort_rec(numlist, n - 1)
    j = n
    while j > 0 and numlist[j - 1] > numlist[j]:
        numlist[j - 1], numlist[j] = numlist[j], numlist[j - 1]
        j -= 1

def ins_sort_while(numlist:list)->None:
    '''
    复杂度为O(n2)
    :param numlist:
    :return:
    '''
    for i in range(1,len(numlist)):
        j = i
        while j > 0 and numlist[j-1] > numlist[j]:
            numlist[j-1] , numlist[j] = numlist[j] , numlist[j-1]
            j -= 1


# 选择排序
def sel_sort_rec(numlist:list, n:int)->None:
    '''
    :param numlist: 排序的数组
    :param n: 数组最后一个元素的序号
    复杂度为O(n2)
    :return:
    '''
    if n == 0:
        return
    ax_j = numlist.index(max(numlist[:n+1]))
    numlist[n], numlist[ax_j] = numlist[ax_j], numlist[n]
    sel_sort_rec(numlist, n - 1)

def sel_sort_while(numlist:list)->None:
    '''
    复杂度为O(n2)
    :param numlist:
    :return:
    '''
    for i in range(len(numlist)-1,0,-1):
        ax_j = numlist.index(max(numlist[:i+1]))
        numlist[i] , numlist[ax_j] = numlist[ax_j] , numlist[i]



# 合并排序
def merge_sort(A:list)->list:
    '''
    复杂度为O(nlogn)
    :param A:
    :return:
    '''
    if len(A) <= 1:
        return A
    middle = len(A) // 2
    leftA = A[:middle]
    rightA = A[middle:]
    leftA_Sorted = merge_sort(leftA)  # 递归分解
    rightA_Sorted = merge_sort(rightA)  # 归分解
    return merge(leftA_Sorted, rightA_Sorted)  # 并问题的分解


def merge(leftS:list, rightR:list)->list:
    i, j = 0, 0
    alist = []
    while i < len(leftS) and j < len(rightR):
        if leftS[i] < rightR[j]:
            alist.append(leftS[i])  # 将元素leftS[i]加入到序列alist中
            i += 1
        else:
            alist.append(rightR[j])  # 将元素rightR[i]加入到序列alist中
            j += 1
    while i < len(leftS):  # 左边剩余数据处理
        alist.append(leftS[i])
        i += 1
    while j < len(rightR):  # 右边剩余数据处理
        alist.append(rightR[j])
        j += 1
    return alist

A = [15,12,21,14,9]
# sel_sort_rec(A,len(A)-1)
# sel_sort_while(A)
# ins_sort_rec(A,len(A)-1)
# ins_sort_while(A)
print(merge_sort(A))
print(A)